#include<iostream>
#include<vector>
using namespace std;
/*
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，
聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。
 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
解题思路：
可以为每个节点设置长度为二的两个状态数组,dp[0]表示偷当前节点所带来的价值，dp[1]表示不透当前节点所带来的价值
然后从二叉树根部开始递归遍历，由于根节点状态依赖于左右孩子的状态，所以递归遍历时采用后根遍历
并且递归终止条件为cur==null
*/
 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
// int rob(TreeNode* root) {
//     vector<int> result = dp(root);
//     return max(result[0],result[1]);
// }
vector<int> dp(TreeNode* cur)
{
    //若当前节点为空，则返回0，0
    if(cur==NULL)
    {
        return vector<int>{0,0};
    }
    //先递归遍历左右子树，并且返回的结果是左右子树的dp数组，两个长度，0代表不偷，1代表偷
    vector<int> left = dp(cur->left);
    vector<int> right = dp(cur->right);
    //遍历完左右子树之后开始遍历当前节点
    //若偷当前节点的话则不不考虑其左右子树
    int a = cur->val+left[0]+right[0];
    //若不偷当前节点的话，则要考虑左右子树，判断左右子树偷和不偷谁的价值更大
    int b = max(left[0],left[1])+max(right[0],right[1]);
    return {a,b};
}
int main()
{
    TreeNode* root =new TreeNode(3);
    root->left =new TreeNode(2);
    root->right = new TreeNode(3);
    TreeNode* cur = root;
    cur = cur->left;
    cur->right=new TreeNode(3);
    cur=root->right;
    cur->right = new TreeNode(1);
    vector<int> result = dp(root);
    cout<<max(result[0],result[1]);
    return 0;
}